Error correction techniques are used in a number of communication and storage systems. Error correction codes, such as Reed-Solomon codes, add one or more redundant bits to a digital stream prior to transmission or storage, so that a decoder can detect and possibly correct errors caused by noise or other interference. One class of error correction codes are referred to as “turbo” codes. Generally, turbo codes employ a combination of two or more systematic convolutional or block codes. Typically, an iterative decoding technique is employed where the output of each decoding step serves as an input to the subsequent decoding step. Turbo encoders typically employ a limited number of programmable choices of block size. The number of bits generated for each input block depends on the size of the input block, as well as the amount of redundancy added by the encoder.
In block coding, the data to be transmitted is broken into smaller blocks and each block is separately encoded. Generally, redundant bits are appended to each block of data. A block code is referred to as an (n, k) code, where n is the total number of bits in the encoded transmission block and k is the number of bits in the unencoded message block. Thus, n-k redundancy bits, also referred to as parity bits, are added to the message block during encoding.
Turbo Product Codes are a well known class of error correction codes that use a block parity mechanism, whereby a number of parity bits are added to each block of data prior to transmission or storage. Product codes generally arrange two dimensional codes (n, k) into (r×c arrays of r rows and c columns. Data is encoded as a two-dimensional codeword. Typically, one row and one column contain parity bits for columns and rows, respectively. The size of the codeword (i.e., the number of rows and columns) directly affects the code rate and the redundancy per user bit. For example, if a codeword size is 20 rows by 20 columns, and one row and one column contain parity bits, each codeword contains 361 bits of user data (400−20−19). The code rate is thus (400−39)/400.
When the amount of data to be transmitted does not completely fill an integer number of codewords, the final codeword is only partially filled with valid data and the code ratesuffers. In addition, system requirements vary so that one codeword size does not satisfy all systems. For example, a number of configurable parameters, such as choice of modulation code, error correction code, sector size, and format efficiency, affect the optimal codeword size for efficient transmission. While one system may transmit or store data in units of 512 bytes, another system may transmit or store data in units of 560 bytes. For example, in a storage application, one storage system may employ a sector size of 512 bytes, and another may employ a sector size of 560 bytes. Meanwhile, a manufacturer of the encoders/decoders employed in such systems does not want to provide a unique encoder/decoder solution for each application.
A need therefore exists for improved methods and apparatus for codeword encoding and decoding over a range of transmission sizes.